package _dp_base;

import java.util.Arrays;

/**
 * 115. 不同的子序列
 */
public class No115 {
    private String s, t;
    private int[][] cache;

    /**
     * 1. 递归
     */
    public int numDistinct1(String s, String t) {
        this.s = s;
        this.t = t;
        int n = s.length();
        int m = t.length();
        cache = new int[n][m];
        for (int[] ints : cache) Arrays.fill(ints, -1);

        return (int) (dfs(n - 1, m - 1) % (Math.pow(10, 9) + 7));
    }

    private int dfs(int i, int j) {
        if (j < 0) return 1;
        else if (cache[i][j] != -1) return cache[i][j];
        boolean eq = s.charAt(i) == t.charAt(j);
        if (i == j && eq) return cache[i][j] = dfs(i - 1, j - 1);
        else if (i > j && eq) return cache[i][j] = dfs(i - 1, j) + dfs(i - 1, j - 1);
        else if (i > j) return cache[i][j] = dfs(i - 1, j);
        else return 0;
    }

    /**
     * 2. 迭代
     */
    public int numDistinct2(String s, String t) {
        int n = s.length();
        int m = t.length();

        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            f[i][0] = 1;
            for (int j = 0; j < m && j <= i; j++) {
                boolean eq = s.charAt(i) == t.charAt(j);
                if (i == j && eq) f[i + 1][j + 1] = f[i][j];
                else if (i > j && eq) f[i + 1][j + 1] = f[i][j + 1] + f[i][j];
                else if (i > j) f[i + 1][j + 1] = f[i][j + 1];
            }
        }

        return (int) (f[n][m] % (Math.pow(10, 9) + 7));
    }

    /**
     * 3. 滚动数组
     */
    public int numDistinct3(String s, String t) {
        int n = s.length();
        int m = t.length();

        int[][] f = new int[2][m + 1];
        for (int i = 0; i < n; i++) {
            f[i % 2][0] = 1;
            for (int j = 0; j < m && j <= i; j++) {
                boolean eq = s.charAt(i) == t.charAt(j);
                if (i == j && eq) f[(i + 1) % 2][j + 1] = f[i % 2][j];
                else if (i > j && eq) f[(i + 1) % 2][j + 1] = f[i % 2][j + 1] + f[i % 2][j];
                else if (i > j) f[(i + 1) % 2][j + 1] = f[i % 2][j + 1];
            }
        }

        return (int) (f[n % 2][m] % (Math.pow(10, 9) + 7));
    }

    /**
     * 4. 一维数组
     */
    public int numDistinct4(String s, String t) {
        int n = s.length();
        int m = t.length();

        int[] f = new int[m + 1];
        f[0] = 1;
        for (int i = 0; i < n; i++) {
            int pre = f[0];
            for (int j = 0; j < m && j <= i; j++) {
                int temp = f[j + 1];
                boolean eq = s.charAt(i) == t.charAt(j);
                if (i == j && eq) f[j + 1] = pre;
                else if (i > j && eq) f[j + 1] = f[j + 1] + pre;
                pre = temp;
            }
        }

        return (int) (f[m] % (Math.pow(10, 9) + 7));
    }
}
